// 优先级队列
// 数组中每次都需要拿到最大元素或者最小元素，可以考虑用堆的思想解决
// top K 问题要想到用堆解决
// top K 问题有可能需要预处理数组，例如统计单词出现的次数，可以借助哈希表完成

// 例题 3：
// 给定一个单词列表 words 和一个整数 k ，返回前 k 个出现次数最多的单词。
// 返回的答案应该按单词出现频率由高到低排序。如果不同的单词有相同出现频率， 按字典顺序 排序。
//
//        示例 1：
//
//        输入: words = ["i", "love", "leetcode", "i", "love", "coding"], k = 2
//        输出: ["i", "love"]
//        解析: "i" 和 "love" 为出现次数最多的两个单词，均为2次。
//        注意，按字母顺序 "i" 在 "love" 之前。
//        示例 2：
//
//        输入: ["the", "day", "is", "sunny", "the", "the", "the", "sunny", "is", "is"], k = 4
//        输出: ["the", "is", "sunny", "day"]
//        解析: "the", "is", "sunny" 和 "day" 是出现次数最多的四个单词，
//        出现次数依次为 4, 3, 2 和 1 次。
//
//
//        注意：
//
//        1 <= words.length <= 500
//        1 <= words[i] <= 10
//        words[i] 由小写英文字母组成。
//        k 的取值范围是 [1, 不同 words[i] 的数量]
//
//
//        进阶：尝试以 O(n log k) 时间复杂度和 O(n) 空间复杂度解决。

// 解题思路：
// 使用哈希表统计单词频次
// 按照频次建立大根堆，按照字典序建立小根堆
// 使元素依次入队
// 取前 k 个元素

import javafx.util.Pair;

import java.util.*;

public class TopKFrequent {
    public List<String> topKFrequent(String[] words, int k) {
        List<String> ret = new ArrayList<>();
        Map<String, Integer> hash = new HashMap<>();
        for(String word : words) hash.put(word, hash.getOrDefault(word, 0) + 1);
        PriorityQueue<Pair<String, Integer>> heap = new PriorityQueue<>((a, b) -> {
            if(a.getValue() != b.getValue()) return b.getValue() - a.getValue();
            else return a.getKey().compareTo(b.getKey());
        });
        for(String s : hash.keySet()){
            heap.offer(new Pair<String, Integer>(s, hash.get(s)));
        }
        for(int i = 0; i < k; i++){
            Pair<String, Integer> p = heap.poll();
            ret.add(p.getKey());
        }
        return ret;
    }
}
